class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        string new_s = '-' + s;//手动添加一个无效字符
        int n = s.size();
        vector<bool> dp(n + 1);//创建dp表

        int n1 = wordDict.size();
        unordered_map<string, int>hash;
        for (int i = 0; i < n1; i++)
        {
            hash[wordDict[i]]++;//使用哈希表统计word中出现的单词
        }
        //初始化
        dp[0] = true;

        //填表
        for (int i = 1; i <= n; i++)
        {
            int j = 0;
            while (j <= i)
            {
                if (dp[j] == true)
                {
                    string tmp(new_s.begin()+1 + j, new_s.begin() + i+1);//使用迭代器将tmp完成赋值
                    //下面是判断tmp是否出现在word中
                    if (hash[tmp] != 0)
                    {
                        dp[i] = true;
                        break;
                    }
                }
                j++;
            }
        }
        return dp[n];
    }
};